package net.zjitc.link;

import net.zjitc.list.MyList;

public class MyLinkedList<T> implements MyList<T> {
     private int size;
     private Node<T> first;
     private Node<T> last;

    /**
     * 默认添加最后
     * @param data
     * @return
     */
    @Override
    public boolean add(T data) {
        Node<T> node = new Node<>(data);
        linkLast(node);
        return true;
    }


    private void linkLast(Node<T> node) {
        if (first == null) {
            first = node;
            last = first;
        } else {
            last.next = node;
            last = last.next;
        }
        size++;
    }

    /**
     * 插入：指定位置插入
     * @param index
     * @param data
     * @return
     */
    @Override
    public boolean add(int index, T data) {
        if (index<0 ||index>size){
            throw new RuntimeException("添加的下标越界");
        }
        //创建一个新的节点
        Node<T> node = new Node<>(data);
        //当添加到最后的情况，last发生变化
        if (index == size){
            linkLast(node);
            return true;
        }
        //添加到最前的情况，first变化
        if (index == 0){
            node.next = first;
            first = node;
            size++;
            return true;
        }

        //添加到中间的位置，（找前一个节点）
        Node<T> p = first;
        for (int i = 0; i < index-1; i++) {
            p = p.next;
        }
        node.next =p.next;
        p.next = node;
        size++;
        return true;
    }

    @Override
    public T remove(T data) {
        //代码补全
        Node<T> p = first;
        Node<T> q = null;
        T oldData = null;
        if (data == null){
            while (p!= null){
                if (p.data == null){
                    if (q == null){
                        first = p.next;
                        p.next = null;
                        size--;
                        oldData = null;
                        break;
                    }
                    q.next = p.next;
                    oldData = p.data;
                    size--;
                    break;
                }
                q =  p;
                p = p.next;

            }
        }else {
            while (p!=null){
                if (data.equals(p.data)){
                    if (q == null){
                        first = p.next;
                        p.next = null;
                        size--;
                        oldData = p.data;
                        break;
                    }
                    q.next = p.next;
                    oldData = p.data;
                    size--;
                    break;
                }
                q =  p;
                p = p.next;

            }
        }
        //删除的最后一个
        if (q!=null && q.next == null){
            last = q;
        }
        return oldData;
    }

    @Override
    public T remove(int index) {
        if (index<0 || index >=size){
            throw new RuntimeException("元素下标越界");
        }
        Node<T> p = first;
        if (index == 0){
            first = p.next;
            p.next = null;
            size--;
            return p.data;
        }
        //删除最后一个节点和删除中间位置的，都是找到删除的前一个
        //不同的地方在于删除最后一个的时候，last发生了变化
        for (int i = 0; i < index-1; i++) {
            p = p.next;
        }
        T oldData = (T) p.next.data;
        p.next = p.next.next;
        if (index == size-1){ //删除最后的时候last的变化
            last = p;
        }
        size--;
        return oldData;
    }

    /**
     * 修改指定索引的Data
     * @param index
     * @param data
     * @return
     */
    @Override
    public boolean set(int index, T data) {
        if (index>=size || index<0){
            throw new RuntimeException("元素下标越界");
        }
        Node<T> p = first;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        p.data = data;
        return true;
    }

    /**
     *获得指定索引的节点数据
     * @param index
     * @return
     */
    @Override
    public T getValue(int index) {
        if (index>=size || index<0){
            throw new RuntimeException("元素下标越界");
        }
        Node<T> p = first;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p.data;
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * 输出所有的Data
     */
    public void printData(){
        /* Node node = first;
       for(int i = 0 ; i < this.size - 1 ;i++){
            System.out.println(node.data);
            node = node.next;
        }*/

        Node node = first;
        while (node!= null){
            System.out.println(node.data);
            node = node.next;
        }
    }
    public  void  nixu() {
        if (first == null || first.next == null){

        }
        Node<Student> before = null;
        Node p = first;
        Node after = null;
        while (p != null) {
            after = p.next;
            p.next = before;
            before = p;
            p = after;
        }
        last = first;
        first = after;
    }
}
